﻿/*
 *  Written by Henning Mortensen 12/7-2010 -> 23/7-2010.
 *  
 * DONE: All conversion functions to be static!
 * DONE: Sorting should handle NAN values!!
 * TODO: Mulighed for at brugere selv kan tilføje Manipulatore
 */

using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;

namespace TGJ_GGA
{
    public class ByteArrayGA
    {
        public List<Gene> Population = new List<Gene>();

        private GAInit GAinitData;
        private Random rnd = new Random((int)(DateTime.Now.Ticks));

        private int currentGenerationNumber = 0;

        //Elitism

        private Gene eliteGene;

        public double[] fractionCurve;

        //Holds all the functions to be used to manipulate the genes
        public ManipulatorHandler manipulatorHandler = new ManipulatorHandler();

        // The one function the users must make them selfs.
        public delegate void FitnessFunction(Gene g);
        public FitnessFunction CalculateFitness;

        // Function(s) the user can make to do stuff to the population for each generation.
        public delegate void ForeachGeneration(int i, List<Gene> pop);
        public ForeachGeneration ForeachStep;

        //default Constructor
        public ByteArrayGA(GAInit gainit, FitnessFunction f, ForeachGeneration fes)
        {
            GAinitData = gainit;

            //Setup space for Selection Probabilities and generate it.
            fractionCurve = new double[GAinitData.populationSize];
            GenerateSelectionCurve(gainit.keep);

            //Setup random generation
            for (int j = 0; j < GAinitData.populationSize; j++)
            {
                Population.Add(GenerateGene());
            }

            eliteGene = GenerateGene();
            eliteGene.fitness = GAinitData.aimForHighFitness == true ? double.MinValue : double.MaxValue;

            //setup calls to the user specifik funktions.
            CalculateFitness += f;// new FitnessFunction(f);
            ForeachStep += fes;// new ForeachGeneration(fes);
        }

        //Generate selection curve.
        private void GenerateSelectionCurve(int nKeep)
        {
            if (nKeep > GAinitData.populationSize)
            {
                nKeep = GAinitData.populationSize;
            }

            double sum = 0;
            for (int j = 1; j <= nKeep; j++)
            {
                sum += j;
            }

            for (int i = 1; i <= nKeep; i++)
            {
                double val = ((double)nKeep - i + 1) / sum;
                fractionCurve[i - 1] = val;
            }

            for (int i = 1; i < nKeep; i++)
            {
                fractionCurve[i] += fractionCurve[i - 1];
            }
        }

        //Returns a deep copy of a gene
        public static Gene CopyGene(Gene g)
        {
            Gene result = new Gene(g.GeneData.Length);
            result.fitness = g.fitness;
            for (int i = 0; i < g.GeneData.Length; i++)
            {
                result.GeneData[i] = g.GeneData[i];
            }
            return result;
        }

        #region Genetic operator funktions
        public Gene ByteCrossover(Gene geneA, Gene geneB)
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);

            int xPoint = rnd.Next(GAinitData.geneSizeInBytes);

            for (int i = 0; i < GAinitData.geneSizeInBytes; i++)
            {
                if (i < xPoint)
                {
                    result.GeneData[i] = geneA.GeneData[i];
                }
                else
                {
                    result.GeneData[i] = geneB.GeneData[i];
                }
            }
            return result;
        }

        public Gene BitCrossover(Gene geneA, Gene geneB)
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);

            int xPoint = rnd.Next(GAinitData.geneSizeInBytes);
            int xBitPoint = rnd.Next(8);

            for (int i = 0; i < GAinitData.geneSizeInBytes; i++)
            {
                if (i < xPoint)
                {
                    result.GeneData[i] = geneA.GeneData[i];
                }
                if (i == xPoint)
                {
                    byte byteResult = 0;
                    if (xBitPoint == 0)
                    {
                        result.GeneData[i] = geneA.GeneData[i];
                    }
                    //bitswap
                    else
                    {
                        byteResult |= (byte)(geneA.GeneData[i] & (255 << xBitPoint));
                        byteResult |= (byte)(geneB.GeneData[i] & ((255 << xBitPoint) ^ 255));
                        result.GeneData[i] = byteResult;
                    }
                }
                if (i > xPoint)
                {
                    result.GeneData[i] = geneB.GeneData[i];
                }
            }
            return result;
        }

        //Flip a single bit in a random byte
        public Gene BitToggle(Gene geneA)
        {
            Gene result = CopyGene(geneA);

            int bytePoint = rnd.Next(GAinitData.geneSizeInBytes);
            int bitPoint = rnd.Next(8);

            byte newByte = result.GeneData[bytePoint];
            newByte = (byte)(newByte ^ (1 << bitPoint));
            result.GeneData[bytePoint] = newByte;

            return result;
        }

        //Flip all bits in a random byte
        public Gene ByteToggle(Gene geneA)
        {
            Gene result = CopyGene(geneA);

            int bytePoint = rnd.Next(GAinitData.geneSizeInBytes);

            result.GeneData[bytePoint] ^= (byte)255;
            return result;
        }

        //Generates a new random gene;
        internal Gene GenerateGene()
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);
            rnd.NextBytes(result.GeneData);
            return result;
        }

        //replaces a part (in byte steps) of the gene with new data. 
        public Gene ByteSubSubstitution(Gene geneA)
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);
            int sPoint = rnd.Next(GAinitData.geneSizeInBytes);
            int sLength = rnd.Next(GAinitData.geneSizeInBytes - sPoint);

            for (int i = 0; i < GAinitData.geneSizeInBytes; i++)
            {
                if (i < sPoint || i >= sPoint + sLength)
                {
                    result.GeneData[i] = geneA.GeneData[i];
                }
                if (i >= sPoint && i < sPoint + sLength)
                {
                    result.GeneData[i] = Convert.ToByte(rnd.Next(256));
                }
            }
            return result;
        }

        //replaces a part (in bit steps) of the gene with new data. 
        public Gene BitSubSubstitution(Gene geneA)
        {
            Gene result = geneA;

            int sPoint = rnd.Next(result.GeneData.Length * 7);
            int sLength = rnd.Next(result.GeneData.Length * 8 - (sPoint + 1)) + 1;

            int startByteIndex = sPoint / 8;
            int startBitindex = sPoint % 8;
            int stopByteIndex = (sPoint + sLength) / 8;
            int stopBitindex = (sPoint + sLength) % 8;
            byte preData = Convert.ToByte(rnd.Next(256));
            byte postData = Convert.ToByte(rnd.Next(256));
            //is selection in same byte
            if (startByteIndex == stopByteIndex)
            {
                byte preMask = (byte)(255 << (8 - startBitindex));
                preMask ^= 255;
                byte postMask = (byte)((255 >> stopBitindex));
                postMask ^= 255;
                byte resultMask = (byte)((preMask & postMask));
                byte NewData = (byte)(rnd.Next(256) & resultMask);
                result.GeneData[startByteIndex] = (byte)((result.GeneData[startByteIndex] & (resultMask ^ 255)) | NewData);
                return result;
            }
            else
            {
                for (int byteIndex = startByteIndex + 1; byteIndex < stopByteIndex; byteIndex++)
                {
                    result.GeneData[byteIndex] = (byte)rnd.Next(256);
                }
                result.GeneData[startByteIndex] &= (byte)(255 << (8 - startBitindex));
                preData &= (byte)((255 >> startBitindex));
                result.GeneData[startByteIndex] |= preData;
                result.GeneData[stopByteIndex] &= (byte)(255 << stopBitindex);
                postData &= (byte)((255 >> stopBitindex) ^ 255);
                result.GeneData[stopByteIndex] |= postData;
            }
            return result;
        }

        //Swap a part of the gene to another location (byte level)
        public Gene ByteSwap(Gene geneA)
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);
            int sPoint = rnd.Next(GAinitData.geneSizeInBytes);
            int sLength = rnd.Next(GAinitData.geneSizeInBytes - sPoint);

            for (int i = 0; i < GAinitData.geneSizeInBytes; i++)
            {
                if (i < sPoint)
                {
                    result.GeneData[i] = geneA.GeneData[i];
                }
                if (i >= sPoint && i < sPoint + GAinitData.geneSizeInBytes - (sPoint + sLength))
                {
                    result.GeneData[i] = geneA.GeneData[i + sLength];
                }
                if (i >= GAinitData.geneSizeInBytes - sLength)
                {
                    result.GeneData[i] = geneA.GeneData[i - (GAinitData.geneSizeInBytes - (sPoint + sLength))];
                }
            }
            return result;
        }

        //Swap a part of the gene to another location (bit level)
        public Gene BitSwap(Gene gene)
        {
            Gene result = new Gene(GAinitData.geneSizeInBytes);
            int sPoint = rnd.Next(GAinitData.geneSizeInBytes * 8);//location in bits
            int sLength = rnd.Next(GAinitData.geneSizeInBytes * 8 - sPoint); //length in bits

            BitArray bitArr = new BitArray(gene.GeneData);
            BitArray resArr = new BitArray(gene.GeneData.Length * 8);

            for (int i = 0; i < GAinitData.geneSizeInBytes * 8; i++)
            {
                if (i < sPoint)
                {
                    resArr[i] = bitArr[i];
                }
                if (i >= sPoint && i < sPoint + GAinitData.geneSizeInBytes * 8 - (sPoint + sLength))
                {
                    resArr[i] = bitArr[i + sLength];
                }
                if (i >= GAinitData.geneSizeInBytes * 8 - sLength)
                {
                    resArr[i] = bitArr[i - (GAinitData.geneSizeInBytes * 8 - (sPoint + sLength))];
                }
            }
            resArr.CopyTo(result.GeneData, 0);
            return result;
        }

        public Gene Substitution(Gene gene)
        {
            return GenerateGene();
        }
        #endregion

        private void Evolve()
        {
            List<Gene> result = new List<Gene>();

            //Makes sure that the elite gene is allways passed on
            if (GAinitData.elitsm == true)
            {
                if (GAinitData.aimForHighFitness == true)
                {
                    if (eliteGene.fitness < Population[0].fitness)
                    {
                        eliteGene = CopyGene(Population[0]);
                    }
                }
                else
                {
                    if (eliteGene.fitness > Population[0].fitness)
                    {
                        eliteGene = CopyGene(Population[0]);
                    }
                }
                result.Add(CopyGene(eliteGene));//Elitsm
            }

            while (result.Count < GAinitData.populationSize)
            {
                Gene GeneA = SelectGene();
                Gene GeneB = SelectGene();
                //Store result in GeneA
                GeneA = manipulatorHandler.run(GeneA, GeneB);

                //Test to see if a clone of teh gene allready exisits?
                if (!GAinitData.allowClones)
                {
                    bool exsistsA = false;
                    foreach (Gene g in result)
                    {
                        if (GeneA.Compare(g, GeneA) == 0)
                        {
                            exsistsA = true;
                        }
                    }
                    if (exsistsA == false) { result.Add(GeneA); }
                }
                else
                {
                    result.Add(GeneA);
                }
            }
            Population = result;
        }

        private Gene SelectGene()
        {
            //selectionFractions
            double rnr = rnd.NextDouble();
            int index = 0;
            while (rnr > fractionCurve[index++]) ;
            return CopyGene(Population[Population.Count - index]);  //sorted in opporsit direction
        }

#region Compare used to sort according to fitness.
        private int CompareHigh(Gene geneA, Gene geneB)
        {
            if (double.IsNaN(geneA.fitness))
            {
                geneA.fitness = double.MinValue;
            }

            if (double.IsNaN(geneB.fitness))
            {
                geneB.fitness = double.MinValue;
            }

            if (geneA == null)
            {
                //if both null they are equal
                if (geneB == null)
                {
                    return 0;
                }
                //if geneB != null the geneB is more than geneA
                else
                {
                    return 1;
                }
            }
            else
            {
                //geneA != null so geneA is more than geneB
                if (geneB == null)
                {
                    return -1;
                }
                else
                {

                    if (geneB.fitness < geneA.fitness)
                    {
                        return -1;
                    }
                    if (geneB.fitness > geneA.fitness)
                    {
                        return 1;
                    }
                    return 0;
                }
            }
        }
        private int CompareLow(Gene geneA, Gene geneB)
        {
            if (double.IsNaN(geneA.fitness))
            {
                geneA.fitness = double.MaxValue;
            }

            if (double.IsNaN(geneB.fitness))
            {
                geneB.fitness = double.MaxValue;
            }

            if (geneA == null)
            {
                //if both null they are equal
                if (geneB == null)
                {
                    return 0;
                }
                //if geneB != null the geneB is more than geneA
                else
                {
                    return 1;
                }
            }
            else
            {
                //geneA != null so geneA is more than geneB
                if (geneB == null)
                {
                    return -1;
                }
                else
                {
                    //ok non af the genes are null.
                    if (geneB.fitness > geneA.fitness)
                    {
                        return -1;
                    }
                    if (geneB.fitness < geneA.fitness)
                    {
                        return 1;
                    }
                    return 0;
                }
            }
        }
#endregion
        
        /// <summary>
        /// Calculate fitness for each gene and sorts them accordenly.
        /// </summary>
        private void EvolutionaryStep()
        {
            foreach (Gene g in Population)
            {
                CalculateFitness(g);
            }

            if (GAinitData.aimForHighFitness)
            {
                Population.Sort(CompareHigh);
            }
            else
            {
                Population.Sort(CompareLow);
            }
            currentGenerationNumber++;
        }

        public Gene Run()
        {
            EvolutionaryStep();
            ForeachStep(currentGenerationNumber, Population);
            Evolve();
            /*
             * Run the main loop of the GA
             */
            while (currentGenerationNumber < GAinitData.numberOfGenerations)
            {
                EvolutionaryStep();
                ForeachStep(currentGenerationNumber, Population);
                Evolve();
            }

            EvolutionaryStep();

            return Population[0];
        }


        #region All Conversion between Byte array and datatypes (Static functions)

        //http://www.yoda.arachsys.com/csharp/floatingpoint.html
        //1 sign
        //11 exponent
        //52 Mantissa
        public static double ReadDouble(ref int i, byte[] arr) //8 bytes
        {
            double result = BitConverter.ToDouble(arr, i);
            i += sizeof(double);
            return result;
        }

        public static sbyte ReadSbyte(ref int i, byte[] arr)   //1 byte
        {
            sbyte result = (sbyte)arr[i++];
            i += sizeof(sbyte);
            return result;
        }

        public static byte ReadByte(ref int i, byte[] arr)   //1 bytes
        {
            return arr[i++];
        }

        public static short ReadShort(ref int i, byte[] arr)   //2 bytes
        {
            Int16 result = BitConverter.ToInt16(arr, i);
            i += sizeof(Int16);
            return result;
        }

        public static ushort ReadUshort(ref int i, byte[] arr)   //2 bytes
        {
            UInt16 result = BitConverter.ToUInt16(arr, i);
            i += sizeof(UInt16);
            return result;
        }

        public static int ReadInt(ref int i, byte[] arr)   //4 bytes
        {
            Int32 result = BitConverter.ToInt32(arr, i);
            i += sizeof(Int32);
            return result;
        }

        public static uint ReadUint(ref int i, byte[] arr)   //4 bytes
        {
            UInt32 result = BitConverter.ToUInt32(arr, i);
            i += sizeof(UInt32);
            return result;
        }

        public static long ReadLong(ref int i, byte[] arr)   //8 bytes
        {
            Int64 result = BitConverter.ToInt64(arr, i);
            i += sizeof(Int64);
            return result;
        }

        public static ulong ReadUlong(ref int i, byte[] arr)   //8 bytes
        {
            UInt64 result = BitConverter.ToUInt64(arr, i);
            i += sizeof(UInt64);
            return result;
        }

        public static char ReadChar(ref int i, byte[] arr)   //2 bytes
        {
            char result = BitConverter.ToChar(arr, i);
            i += sizeof(char);
            return result;
        }

        //1 sign
        //8 exponent
        //23 Mantissa
        public static float ReadFloat(ref int i, byte[] arr) //4 bytes
        {
            float result = BitConverter.ToSingle(arr, i);
            i += sizeof(float);
            return result;
        }

        //A decimal is stored in 128 bits, even though only 102 are strictly necessary.
        //It is convenient to consider the decimal as three 32-bit integers representing
        //the mantissa, and then one integer representing the sign and exponent.
        //The top bit of the last integer is the sign bit (in the normal way,
        //with the bit being set (1) for negative numbers) and bits 16-23 (the low bits of
        //the high 16-bit word) contain the exponent. The other bits must all be clear (0).
        //This representation is the one given by decimal.GetBits(decimal) which returns an array of 4 ints
        public static decimal ReadDecimal(ref int i, byte[] arr) //16 bytes
        {
            int low = 0;
            int mid = 0;
            int high = 0;
            bool sign = false;
            byte exp = 0;

            byte[] data = new byte[16];
            for (int j = 0; j < 16; j++)
                data[j] = arr[i + j];

            using (MemoryStream stream = new MemoryStream(data))
            {
                using (BinaryReader reader = new BinaryReader(stream))
                {
                    low = reader.ReadInt32();
                    mid = reader.ReadInt32();
                    high = reader.ReadInt32();
                    sign = reader.ReadBoolean();
                    exp = reader.ReadByte();
                }
            }
            exp &= 31;
            if (exp >= 29) exp = 28;

            i += 16;
            return new decimal(low, mid, high, sign, exp);
        }

        #endregion

        #region Serialize
        public static void SerializeToDisk(string filename, Gene g)
        {
            FileStream outStream = File.OpenWrite(filename);
            BinaryWriter bw = new BinaryWriter(outStream);
            foreach (byte b in g.GeneData)
            {
                bw.Write(b);
            }
            bw.Flush();
            bw.Close();
        }

        public static Gene SerializeFromDisk(string filename)
        {
            Gene g = null;

            FileInfo fi = new FileInfo(filename);
            if (fi.Exists)
            {
                FileStream inStream = File.OpenRead(filename);
                BinaryReader br = new BinaryReader(inStream);
                g = new Gene((int)fi.Length);
                br.Read(g.GeneData, 0, (int)fi.Length);
                br.Close();
            }
            return g;
        }

        #endregion

    }

    /// <summary>
    /// Helper class to hold all of the initalization data for the GA
    /// </summary>
    public class GAInit
    {
        //GA information
        public int numberOfGenerations;         //Maximum number of generations to run
        public int populationSize;              //Number of genes in each generation
        public int geneSizeInBytes;             //Size of gene in bytes
        public bool elitsm;
        public bool aimForHighFitness;          //If true then find the highest fitness (sort to set lowest to top of list)
        public int keep;                        //how many genes to keep out of the total pop
        public bool allowClones;
    }

    public class Gene : IComparer
    {
        public Gene(int size)
        {
            GeneData = new byte[size];
        }
        public byte[] GeneData;
        public double fitness;

        //Compair function to make sure that 2 genes data are not the same!
        public int Compare(object x, object y)
        {
            Gene g1 = (Gene)x;
            Gene g2 = (Gene)y;

            int index = g1.GeneData.Length - 1;

            while (index >= 0 && ((g1.GeneData[index] % 4) == (g2.GeneData[index] % 4))) { index--; }

            if (index == -1)
            {
                //        Console.WriteLine("g1==g2");
                return 0;
            }
            //   Console.WriteLine("g1!=g2");
            return -1;
        }
    }
}
